﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace DiscreteEventModel.Common {

    public class PriorityQueue<T> : ICollection, ICollection<T>, IComparer<T>
        where T : ITokenizable<int> {

        class DefaultComparer<T> : IComparer<T> where T : IComparable<T> {

            public static DefaultComparer<T> Instance = new DefaultComparer<T>();

            private DefaultComparer() { }

            public int Compare(T x, T y) {
                return x.CompareTo(y);
            }
        }

        private IComparer<T> _comparer;
        private List<T> _entries;

        private PriorityQueue(IComparer<T> comparer) {
            this._comparer = comparer;
            this._entries = new List<T>();
        }

        public static PriorityQueue<T> Create(IComparer<T> comparer) {
            return new PriorityQueue<T>(comparer);
        }

        public static PriorityQueue<T> Create<T>()
            where T : ITokenizable<int>, IComparable<T> {
            return new PriorityQueue<T>(DefaultComparer<T>.Instance);
        }

        public int Count {
            get {
                return this._entries.Count;
            }
        }

        private void SetEntry(T entry, int index) {
            this._entries[index] = entry;
            entry.Token = index;
        }

        private bool Contains(T item, out int index) {
            index = item.Token;
            return index >= 0 && index < this._entries.Count && object.ReferenceEquals(this._entries[index], item);
        }

        public bool Contains(T entry) {
            int index;
            return this.Contains(entry, out index);
        }

        private bool RequeueUp(int index) {
            T entry = this._entries[index];
            int newIndex = index;
        REPEAT: {
                if(newIndex > 0) {
                    int superIndex = (newIndex - 1) >> 2;
                    if(this._comparer.Compare(this._entries[superIndex], entry) < 0) {
                        this.SetEntry(this._entries[superIndex], newIndex);
                        newIndex = superIndex;
                        goto REPEAT;
                    }
                }
            }

            if(newIndex == index) {
                return false;
            }
            this.SetEntry(entry, newIndex);
            return true;
        }

        private bool RequeueDown(int index) {
            T entry = this._entries[index];
            int newIndex = index;
        REPEAT: {
                int subIndex = (newIndex << 2) + 1;
                if(subIndex < this._entries.Count) {
                    int maxSubIndex = subIndex;
                    if(++subIndex < this._entries.Count) {
                        if(this._comparer.Compare(this._entries[subIndex], this._entries[maxSubIndex]) > 0) {
                            maxSubIndex = subIndex;
                        }
                        if(++subIndex < this._entries.Count) {
                            if(this._comparer.Compare(this._entries[subIndex], this._entries[maxSubIndex]) > 0) {
                                maxSubIndex = subIndex;
                            }
                            if(++subIndex < this._entries.Count) {
                                if(this._comparer.Compare(this._entries[subIndex], this._entries[maxSubIndex]) > 0) {
                                    maxSubIndex = subIndex;
                                }
                            }
                        }
                    }
                    if(this._comparer.Compare(this._entries[maxSubIndex], entry) > 0) {
                        this.SetEntry(this._entries[maxSubIndex], newIndex);
                        newIndex = maxSubIndex;
                        goto REPEAT;
                    }
                }
            }

            if(newIndex == index) {
                return false;
            }
            this.SetEntry(entry, newIndex);
            return true;
        }

        public bool Enqueue(T entry) {
            int index;
            if(this.Contains(entry, out index)) {
                if(!this.RequeueUp(index)) {
                    this.RequeueDown(index);
                }
                return false;
            } else {
                index = this._entries.Count;
                this._entries.Add(entry);
                entry.Token = index;
                this.RequeueUp(index);
                return true;
            }
        }

        private void Dequeue(int index) {
            this._entries[index].Token = -1;
            int lastIndex = this._entries.Count - 1;
            if(index == lastIndex) {
                this._entries.RemoveAt(index);
            } else {
                this.SetEntry(this._entries[lastIndex], index);
                this._entries.RemoveAt(lastIndex);
                this.RequeueDown(index);
            }
        }

        public bool Dequeue(T entry) {
            int index;
            if(!this.Contains(entry, out index)) {
                return false;
            }

            this.Dequeue(index);
            return true;
        }

        public bool Dequeue(out T entry) {
            if(this._entries.Count == 0) {
                entry = default(T);
                return false;
            }

            entry = this._entries[0];
            this.Dequeue(0);
            return true;
        }

        public void Replace(T entry, T newEntry) {
            int index;
            if(!this.Contains(newEntry, out index)) {
                if(this.Contains(entry, out index)) {
                    this.SetEntry(newEntry, index);
                    if(!this.RequeueUp(index)) {
                        this.RequeueDown(index);
                    }
                }
            }
        }

        public bool Peek(out T entry) {
            if(this._entries.Count == 0) {
                entry = default(T);
                return false;
            }
            entry = this._entries[0];
            return true;
        }

        public void Clear() {
            this._entries.Clear();
        }

        public void TrimExcess() {
            this._entries.TrimExcess();
        }

        #region IEnumerable<T> Members

        public IEnumerator<T> GetEnumerator() {
            return this._entries.GetEnumerator();
        }

        #endregion

        #region IEnumerable Members

        IEnumerator IEnumerable.GetEnumerator() {
            return this._entries.GetEnumerator();
        }

        #endregion

        #region ICollection Members

        void ICollection.CopyTo(Array array, int index) {
            (this._entries as ICollection).CopyTo(array, index);
        }

        bool ICollection.IsSynchronized {
            get {
                return (this._entries as ICollection).IsSynchronized;
            }
        }

        object ICollection.SyncRoot {
            get {
                return (this._entries as ICollection).SyncRoot;
            }
        }

        #endregion

        #region ICollection<T> Members

        public void Add(T entry) {
            this.Enqueue(entry);
        }

        public void CopyTo(T[] array, int arrayIndex) {
            this._entries.CopyTo(array, arrayIndex);
        }

        public bool IsReadOnly {
            get { return false; }
        }

        public bool Remove(T entry) {
            return this.Dequeue(entry);
        }

        #endregion

        #region IComparer<T> Members

        public int Compare(T x, T y) {
            return this._comparer.Compare(x, y);
        }

        #endregion
    }

}
